
//84.柱状图中最大的矩形
class Solution {
public:
    int largestRectangleArea(vector<int>& nums) {
        //需要知道每一个位置向左向右的宽度
        //使用两次单调栈来求最大宽度
        int n=nums.size();
        vector<int> right(n,n);  //right中存储扩展不了的位置
        stack<pair<int,int>> st;  //存储还没有找到位置的元素大小以及下标
        for(int i=0;i<n;i++)
        {
            while(!st.empty()&&st.top().first>nums[i])
            {
                int index=st.top().second;
                right[index]=i;    
                st.pop();
            }

            st.push({nums[i],i});
        }
        vector<int> left(n,-1);  //left中存储先做扩展不到的位置
        while(!st.empty()) st.pop();
        for(int i=n-1;i>=0;i--)
        {
            while(!st.empty()&&st.top().first>nums[i])
            {
                int index=st.top().second;
                left[index]=i;
                st.pop();
            }

            st.push({nums[i],i});
        }

        int ret=0;
        for(int i=0;i<n;i++)
            ret=max(ret,nums[i]*(right[i]-left[i]-1));
        return ret;
    }
};